package leetcode.f1t100;

import leetcode.struct.ListNode;

import java.util.PriorityQueue;

/**
 * 合并K个有序链表
 * https://leetcode.com/problems/merge-k-sorted-lists/
 *
 * @author lichx
 * @date 2021/12/3 14:42
 */
public class Q23_MergeKSortList {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1, new ListNode(4, new ListNode(5, null)));
        ListNode node2 = new ListNode(1, new ListNode(3, new ListNode(4, null)));
        ListNode node3 = new ListNode(2, new ListNode(6, null));
        ListNode[] lists = new ListNode[]{node1, node2, node3};
        ListNode node = merge(lists);
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }

    public static ListNode merge(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        ListNode head = new ListNode(0), cur = head;
        int size = lists.length;
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(size, (o1, o2) -> o1.val - o2.val);
        // init nexts
        for (int i = 0; i < size; i++) {
            if (lists[i] != null) {
                queue.add(lists[i]);
            }
        }
        while (queue.size() > 0) {
            ListNode pollNode = queue.poll();
            cur.next = pollNode;
            cur = cur.next;
            if (pollNode.next != null) {
                queue.add(pollNode.next);
            }
        }
        return head.next;
    }
}
